39.1 KB · ⇊ 12 parts · ⤓ Micron 39.1 KB · ⤓ HTML 127.5 KB

top

Un mwbqRB-Albero (o anche mwbgred-black tree, in italiano mwbwalbero rosso-nero) è un tipo di mwcaalbero binario di ricerca bilanciato, una mwcqstruttura dati usata in mwcgInformatica, tipicamente utilizzata per implementare mwcwinsiemi o mwdaarray associativi. La struttura originale è stata inventata nel mwdq1972 da mwdgRudolf Bayer che la chiamò "B-alberi binari simmetrici", ma ha acquisito il nome attuale a partire da un articolo del mwdw1978 di Leo J. Guibas e mweaRobert Sedgewick. È complessa, ma ha un eccellente mweqtempo di esecuzione nel caso peggiore ed è molto efficiente: effettua ricerche, inserimenti e cancellazioni in un tempo di mweg O ( log ⁡ ⁡ n ) {\displaystyle O(\log n)} , dove mwew n {\displaystyle n} è il numero di elementi nell'albero.

• Concetti di base e terminologia

• Utilizzi e vantaggi

• Proprietà

• Operazioni

• Inserimento

• Cancellazione

• Dimostrazione dei limiti asintotici

• Estensione di RB-Alberi

• Note

• Bibliografia

• Altri progetti

• Collegamenti esterni

• Dimostrazioni

• Implementazioni

Un albero rosso-nero è un tipo speciale di mwfwalbero binario, che è una struttura utilizzata in mwgainformatica per organizzare mwgqdati comparabili, ad esempio numeri. Ciascuna unità di dati è conservata in un mwggnodo. Uno dei nodi funge sempre da punto di partenza, e non è figlio di nessun nodo; viene di solito chiamato mwgwnodo root o semplicemente root. Questo nodo ha al massimo due mwhafigli, ovvero altri nodi ai quali è connesso. Ciascuno di questi figli ha a sua volta al massimo due figli, e così via. Il nodo root inoltre ha un mwhqpath (percorso) che lo collega a qualsiasi altro nodo nell'albero.

Se un nodo non ha figli, viene chiamato mwhwnodo foglia, poiché, intuitivamente, fa parte della "periferia" dell'albero. Un sottoalbero è una porzione dell'albero che si estende a partire da un dato nodo. Negli alberi rosso-neri, si assume che le foglie abbiano valore mwianull, ovvero esse non contengono dati.

Poiché gli alberi rosso-neri sono anche alberi binari di ricerca, essi soddisfano il vincolo per cui ogni nodo contiene un valore minore o uguale a quello di tutti i nodi del suo sottoalbero destro, e maggiore o uguale a quello di tutti i nodi del suo sottoalbero sinistro. Ciò rende veloce la ricerca di un dato valore nell'albero, e consente un mwigordinamento efficiente degli elementi.

Gli alberi rosso-neri, assieme agli mwjqalberi AVL, offrono le migliori performance nel mwjgcaso peggiore dei tempi di ricerca, inserimento e cancellazione. Ciò li rende non soltanto importanti nelle applicazioni mwjwsistema real-time, ma fondamentali "mattoni" di altre strutture dati che forniscono garanzie nel caso peggiore; ad esempio, molte strutture dati usate nella mwkageometria computazionale sono basate su alberi rosso-neri.

Gli alberi rosso-neri sono inoltre importanti nella mwkgprogrammazione funzionale, in cui sono una delle mwkwstrutture dati persistenti più comuni, utilizzati per costruire mwlaarray associativi e mwlqset in grado di mantenere stati precedenti alla modifica. La versione persistente degli alberi rosso-neri richiede uno spazio di O(log mwlgn) per ciascun inserimento o cancellazione, in aggiunta al tempo.

Gli alberi rosso-neri sono un'mwmaisometria degli alberi 2-3-4. In altre parole, per ciascun albero 2-3-4, esiste almeno un albero rosso-nero con gli elementi nello stesso ordine. Le operazioni di inserimento e cancellazione sugli alberi 2-3-4 sono equivalenti a quelle di mwmgricolorazione e mwmwmwnarotazione negli alberi rosso-neri. Gli alberi 2-3-4, dunque, sono uno strumento importante per comprendere la logica esistente dietro gli alberi rosso-neri, ed è questo il motivo per cui molti testi sugli algoritmi introducono gli alberi 2-3-4 subito prima di quelli rosso-neri, benché quelli 2-3-4 non vengano quasi mai utilizzati nella pratica.

Un albero rosso-nero è un mwowalbero binario di ricerca in cui ciascun nodo ha un attributo mwpacolore, il cui valore può essere mwpqrosso oppure mwpgnero. In aggiunta ai requisiti ordinari per un albero binario di ricerca, un albero rosso-nero soddisfa le seguenti proprietà:

1. Ogni nodo ha colore rosso o nero.

2. Il nodo root inizialmente è nero.

3. Ogni foglia è nera e contiene elemento mwqwnull;

4. Entrambi i figli di ciascun nodo rosso sono neri;

5. Ogni cammino da un nodo a una foglia nel suo sottoalbero contiene lo stesso numero di nodi neri.

Questi vincoli rafforzano una proprietà critica degli alberi rosso-neri: che il cammino più lungo dal nodo root a una foglia è al massimo lungo il doppio del cammino più breve. Ne risulta dunque un albero fortemente bilanciato. Poiché le operazioni di ricerca di un valore, inserimento e cancellazione richiedono un tempo di esecuzione nel caso peggiore proporzionale all'altezza dell'albero, questo limite superiore teorico sull'altezza rende gli alberi rosso-neri molto efficienti nel caso peggiore, al contrario di quanto accade con gli ordinari alberi binari di ricerca.

Per vedere in che modo tali proprietà vengono garantite, è sufficiente notare che nessun cammino può avere due nodi rossi in fila, per la proprietà 4. Il cammino più breve possibile ha tutti nodi neri, e il più lungo alterna nodi rossi e nodi neri. Poiché tutti i cammini massimi hanno lo stesso numero di nodi neri, per la proprietà 5, ciò dimostra che nessun cammino è lungo più del doppio di qualsiasi altro cammino.

In molte strutture dati "alberi", è possibile che un nodo abbia un solo figlio, e che i nodi foglia contengano dati. È possibile presentare anche gli alberi rosso-neri secondo questo paradigma, ma ciò modificherebbe alcune delle proprietà e complicherebbe l'algoritmo. Per questa ragione, in questo articolo parliamo di "foglie nulle", che non contengono dati e servono semplicemente ad indicare dove finisce l'albero. Questi nodi vengono spesso omessi nella rappresentazione grafica, e l'albero rappresentato sembra contraddire i principi esposti, ma di fatto non è così. La conseguenza è che tutti i nodi interni (non foglia) hanno due figli, sebbene uno o entrambi questi figli possano essere una foglia nulla.

Alcune trattazioni illustrano gli alberi rosso-neri come alberi binari di ricerca i cui archi (invece dei nodi) sono colorati di rosso o di nero; ma ciò non fa alcuna differenza. Nella nostra terminologia, il colore di un nodo corrisponde al colore dell'arco che connette il nodo al padre, escluso il nodo root che è sempre nero (proprietà 2) in considerazione del fatto che l'arco corrispondente non esiste.

Le operazioni di lettura su un albero rosso-nero non richiedono modifiche rispetto a quelle utilizzate per gli alberi binari di ricerca, poiché gli alberi rosso-neri sono una loro specializzazione. Al contrario, il risultato immediato di un inserimento o di una cancellazione può violare le proprietà dell'albero rosso-nero, e ristabilire tali proprietà richiede un piccolo numero (mwtaO(log mwtqn) o O(1) ammortizzato) di ricolorazioni (che sono molto veloci nella pratica) e non più di tre mwtwrotazioni dell'albero (due per l'inserimento). Nonostante l'inserimento e la cancellazione siano operazioni complicate, i loro tempi di esecuzione rimangono dell'ordine di O(log mwuan).

Si comincia aggiungendo un nodo come se si trattasse di un mwuwalbero binario di ricerca classico, e colorandolo di rosso. Il passo successivo dipende dal colore degli altri nodi attigui. Useremo il termine mwvanodo zio per riferirci al fratello del nodo padre. Si noti che:

• la proprietà 3 (tutte le foglie, incluse quelle nulle, sono nere) persiste;

• la proprietà 4 (entrambi i figli di ogni nodo rosso sono neri) è minacciata soltanto dall'inserimento di un nodo rosso, dalla ricolorazione in rosso di un nodo nero, o da una rotazione;

• la proprietà 5 (tutti i cammini a partire da un dato nodo verso le sue foglie contengono lo stesso numero di nodi neri) è minacciata soltanto dall'inserimento di un nodo nero, dalla ricolorazione in nero di un nodo rosso, o da una rotazione.

mwwwNota: utilizzeremo la seguente simbologia: mwxaN per il nodo inserito, mwxqP per il nodo padre di mwxgN, mwxwG per il nodo padre di mwyaP, e mwyqU per il "nodo zio" di mwygN. Si noti che in qualche caso è possibile che ruoli e simboli dei nodi vengano scambiati; in ogni caso, ciascun simbolo continua a rappresentare lo stesso nodo che rappresentava all'inizio del caso.

Ciascun caso viene dimostrato con del codice d'esempio in mwzalinguaggio C, i nodi "zio" e "nonno" si trovano tramite le seguenti funzioni:

il nuovo nodo mwtqN è nella root dell'albero. In questo caso, viene colorato di nero per soddisfare la proprietà 2 (la root è nera). Poiché questo inserimento aggiunge un nodo nero a ciascun cammino, la proprietà 5 (tutti i cammini a partire da un dato nodo verso le sue foglie contengono lo stesso numero di nodi neri) non è violata.

il padre mw5qP del nuovo nodo è nero, quindi la proprietà 4 (entrambi i figli di ogni nodo rosso sono neri) non è invalidata. In questo caso, l'albero è ancora valido. La proprietà 5 (tutti i cammini a partire da un dato nodo verso le sue foglie contengono lo stesso numero di nodi neri) sembrerebbe minacciata, perché il nuovo nodo mw5gN ha due foglie nere, ma poiché mw5wN è rosso, i cammini attraverso ognuno dei suoi figli hanno lo stesso numero di nodi neri poiché sono cammini separati, per cui la proprietà rimane soddisfatta.

mwarqNota: nei casi che seguono si assume che mwaruN abbia un nodo "nonno" mwaryG, perché il padre mwarcP è rosso, e se fosse stato root sarebbe stato nero. Inoltre, mwargN ha anche un nodo "zio" mwarkU, sebbene esso possa essere una foglia nei casi 4 e 5.

se sia il padre mwaseP sia lo zio mwasiU sono rossi, allora è possibile ricolorare entrambi di nero e ricolorare di rosso il nonno mwasmG per mantenere la proprietà 5 (tutti i cammini a partire da un dato nodo verso le sue foglie contengono lo stesso numero di nodi neri). Adesso il nuovo nodo mwasqN ha un padre nero. Poiché qualsiasi cammino attraverso il padre o lo zio deve passare attraverso il nonno, il numero di nodi neri su questi cammini non cambia. Però il nonno mwasuG ora potrebbe violare la proprietà 2 (il nodo root è nero) o la 4 (entrambi i figli di ogni nodo rosso sono neri) perché potrebbe avere un padre rosso. Per risolvere il problema, la procedura va ripetuta ricorsivamente su mwasyG a partire dal caso 1. Si noti che questa è l'unica chiamata ricorsiva, e che avviene prima di qualsivoglia rotazione, il che prova che si avrà un numero costante di rotazioni.

mwaygNota: nei casi seguenti, si assume che il nodo padre mwaykP è figlio sinistro del proprio padre. Se fosse figlio destro, mwayoleft e mwaysright dovrebbero essere invertiti nei casi 4 e 5.

il padre mwazmP è rosso ma lo zio mwazqU è nero; il nuovo nodo mwazuN è il figlio destro di mwazyP, e mwazcP a sua volta è figlio sinistro di mwazgG. In questo caso, si effettua una mwazkrotazione a sinistra che scambia i ruoli del nuovo nodo mwazoN e del padre mwazsP; quindi ci si occupa dell'ex nodo padre mwazwP utilizzando il caso 5 (scambiando i nomi mwaz0N e mwaz4P). Ciò fa sì che alcuni cammini (quelli etichettati con "1" nel grafico) passino ora attraverso il nuovo nodo senza che prima ciò accadesse; ma entrambi questi nodi sono rossi, perciò la proprietà 5 (tutti i cammini a partire da un dato nodo verso le sue foglie contengono lo stesso numero di nodi neri) non è violata. La proprietà 4 (entrambi i figli di ogni nodo rosso sono neri) è ancora violata, ma si può risolvere continuando con il caso 5.

il padre mwah8P è rosso ma il nonno mwaiaG e lo zio mwaieU sono neri, il nuovo nodo mwaiiN è il figlio sinistro di mwaimP, e mwaiqP è il figlio sinistro di mwaiuG. In questo caso, si effettua una mwaiyrotazione a destra su mwaicG; il risultato è un albero in cui l'ex padre mwaigP è ora il padre sia del nuovo nodo mwaikN sia dell'ex nonno mwaioG. Sappiamo che mwaisG è nero, perché altrimenti il suo ex figlio mwaiwP non avrebbe potuto essere rosso. Si scambiano dunque i colori di mwai0P e mwai4G, e l'albero che ne risulta soddisfa la proprietà 4 (entrambi i figli di ogni nodo rosso sono neri). La proprietà 5 (tutti i cammini a partire da un dato nodo verso le sue foglie contengono lo stesso numero di nodi neri) resta a sua volta soddisfatta, poiché tutti i cammini che prima attraversavano uno di questi tre nodi passavano prima attraverso mwai8G , ora attraverso mwajaP. In ogni caso, è il solo nodo nero dei tre.

Si noti che tutte le chiamate nel codice utilizzano la mwaparicorsione in coda.

In un normale mwapmalbero binario di ricerca, quando si cancella un nodo che ha due figli non-foglia, ci si può trovare in due situazioni: o il valore massimo si trova nel suo sottoalbero sinistro o il valore minimo si trova nel suo sottoalbero destro, quindi si sposta tale valore nel nodo che si vuole cancellare. A questo punto si cancella il nodo da cui abbiamo copiato il valore, di cui si devono avere meno di due figli non-foglia. Poiché copiare semplicemente un valore non viola nessuna proprietà rosso-nera, il problema si riduce a quello di cancellare un nodo con al massimo un figlio. Non importa se il nodo è quello che si voleva eliminare inizialmente o il nodo di cui si è copiato il valore.

Se si sta cancellando un nodo rosso, lo si sostituisce semplicemente con suo figlio, che dev'essere nero. Tutti i cammini che attraversavano il nodo cancellato adesso passeranno attraverso un nodo rosso in meno, e sia il padre che il figlio del nodo cancellato devono essere neri, perciò le proprietà 3 (tutte le foglie, incluse quelle nulle, sono nere) e 4 (entrambi i figli di ogni nodo rosso sono neri) sono ancora valide. Un altro caso semplice è quando il nodo cancellato è nero e suo figlio è rosso. La cancellazione di un nodo nero potrebbe violare le proprietà 4 (entrambi i figli di ogni nodo rosso sono neri) e 5 (tutti i cammini a partire da un dato nodo verso le sue foglie contengono lo stesso numero di nodi neri), ma se si ricolora il figlio di nero, entrambe le proprietà sono mantenute.

Il caso complesso è quando sia il nodo da cancellare sia il figlio sono neri. Il primo passo è sostituire il nodo da eliminare con il figlio. Si chiamerà quindi mwapyN il figlio nella nuova posizione e mwapcS suo fratello (l'altro figlio del suo nuovo padre). Nel diagramma qui sotto, noi useremo anche mwapgP per indicare il nuovo padre di mwapkN, e si mwapoN è figlio sinistro, mwapsC come figlio sinistro di mwapwS e mwap0D per il figlio destro; si mwap4N è figlio destro, mwap8C come figlio destro di mwaqaS e mwaqeD per il figlio sinistro. (È chiaro che mwaqiS non può essere una foglia.)

mwaquAttenzione: tra i due casi, scambiamo ruoli e label dei nodi, ma in ogni caso, ogni label continua a rappresentare lo stesso nodo che rappresentava all'inizio del caso. Qualsiasi colore mostrato nel diagramma è supposto o implicato dalle precedenti ipotesi. Il bianco rappresenta un colore sconosciuto (indifferentemente rosso o nero).

Troveremo i fratelli usando questa funzione:

Possiamo svolgere i passi descritti sopra con l'uso del seguente codice, dove la funzione mwatoreplace_node sostituisce mwatschild nella posizione mwatwn dell'albero. Per convenienza, il codice presentato in questa sezione presupporrà che le foglie nulle siano rappresentate da oggetti nodo, piuttosto che da NULL (il codice della sezione mwat0Inserimento funziona in entrambi i casi).

mwa0uAttenzione: Se mwa0yN è una foglia nulla e non la vogliamo rappresentare come oggetto nodo, possiamo modificare l'algoritmo chiamando prima delete_case1() sul padre (il nodo che vogliamo cancellare, mwa0cn nel codice riportato sopra) e cancellarlo dopo. Possiamo farlo perché il padre è nero, quindi si comporta allo stesso modo di una foglia nulla (chiamata a volte foglia 'fantasma'). E possiamo cancellarlo senza rischi alla fine, visto che mwa0gn rimarrà foglia dopo tutte le operazioni, come mostrato sopra.

Se sia mwa0oN che il padre originale sono neri, cancellare il padre farà in modo che i percorsi attraverso mwa0sN abbiano un nodo nero in meno rispetto ai percorsi che non ci passano. Dal momento che questa situazione violerebbe la proprietà 5 (Tutti i percorsi da un qualsiasi nodo alle foglie sottostanti contengono lo stesso numero di nodi neri), l'albero deve essere ribilanciato. Ci sono molti casi da considerare.

mwa08N è la nuova root. In questo caso, abbiamo finito. Abbiamo rimosso un nodo nero da ogni percorso, e la nuova root è nera, quindi tutte le proprietà sono soddisfatte.

mwa3gAttenzione: Nei casi 2, 5, e 6, supponiamo che mwa3kN sia il figlio sinistro del proprio padre mwa3oP. Se fosse il figlio destro, mwa3sdestro e mwa3wsinistro andrebbero invertiti nel seguito della discussione. Di nuovo, il codice di esempio tiene conto di entrambi i casi.

mwa4qS è rosso. In questo caso invertiamo i colori di mwa4uP e mwa4yS, ed effettuiamo una mwa4crotazione a sinistra su mwa4gP, facendo ruotare mwa4kS nel nonno di mwa4oN. Notare che mwa4sP deve essere nero, visto che ha un figlio rosso. Nonostante tutti i percorsi abbiano lo stesso numero di nodi neri, ora mwa4wN ha un fratello nero ed un padre rosso, quindi possiamo procedere con i passi 4, 5, o 6 (il nuovo fratello è nero perché era una volta il figlio del rosso mwa40S). Nell'ultimo caso, rietichettiamo mwa44S come nuovo fratello di mwa48N.

mwa-qP, mwa-uS, ed il figlio di mwa-yS sono neri. In questo caso, semplicemente ricoloriamo mwa-cS di rosso. Il risultato è che tutti i percorsi che passano da mwa-gS, ovvero tutti quelli non passanti da mwa-kN, hanno un nodo nero in meno. Visto che cancellare il padre originale di mwa-oN toglie un nodo nero ai percorsi che passano da mwa-sN, le cose sono aggiustate. Comunque, tutti i percorsi che passano da mwa-wP ora hanno un nero in meno di quelli che non ci passano, quindi la proprietà 5 (Tutti i percorsi da un qualsiasi nodo alle foglie sottostanti contengono lo stesso numero di nodi neri) è ancora violata. Per correggere questo problema rieseguiamo la bilanciatura su mwa-0P, ripartendo dal caso 1.

mwbgwS ed il suo figlio sono neri, ma mwbg0P è rosso. In questo caso scambiamo i colori di mwbg4S e mwbg8P. Questa mossa non modifica il numero di neri nei percorsi che non passano da mwbhaN, ma ne aggiunge uno a quelli che ci passano, permettendo la cancellazione di un nodo nero in quei percorsi.

mwbomS è nero, il figlio sinistro di mwboqS è rosso, quello destro è nero, e mwbouN è il figlio sinistro del proprio padre. In questo caso ruotiamo a destra su mwboyS, in modo che il figlio sinistro di mwbocS ne diventi il padre, ed mwbogN il nuovo fratello. Scambiamo i colori di mwbokS e del suo nuovo padre. Tutti i percorsi hanno ancora lo stesso numero di nodi neri, ma ora mwbooN ha un fratello nero il cui figlio destro è rosso, così ricadiamo nel caso 6. Né mwbosN né il suo padre vengono modificati da questa trasformazione.

(Ancora, per il caso 6, rietichettiamo mwbo0S come nuovo fratello di mwbo4N).

mwbckS è nero, il suo figlio destro è rosso, e mwbcoN è il figlio sinistro del proprio padre mwbcsP. In questo caso effettuiamo una rotazione a sinistra su mwbcwP, in modo che mwbc0S diventi padre di mwbc4P e del figlio destro di mwbc8S. Scambiamo i colori di mwbdaP e mwbdeS, e coloriamo il figlio destro di mwbdiS di nero. Il sottoalbero avrà lo stesso colore della propria root, cosicché le proprietà 4 (Entrambi i figli di un nodo rosso sono neri) e 5 (Tutti i percorsi da un qualsiasi nodo alle foglie sottostanti contengono lo stesso numero di nodi neri) non vengono violate. Comunque, mwbdmN ha un antenato nero in più: sia che mwbdqP sia divento nero, sia che era nero e mwbduS è stato aggiunto come nonno nero. Per cui i percorsi che attraversano mwbdyN incontrano un nero in più.

Contemporaneamente, se un percorso non attraversa mwbdgN, ci sono due possibilità:

• Attraversa il nuovo fratello di mwbdsN. Per cui deve attraversare mwbdwS e mwbd0P, sia prima che dopo le modifiche, che si sono semplicemente scambiati il colore (ovvero il numero di neri non è cambiato).

• Attraversa il nuovo zio di mwbd8N, figlio destro di mwbeaS. In questo caso, prima attraversava mwbeeS, il padre di mwbeiS, ed il figlio destro di mwbemS, ma ora attraversa solo mwbeqS, che ha preso il colore dell'ex padre, ed il figlio destro di mwbeuS, modificato da rosso a nero. Il risultato è che il numero di neri non è cambiato.

In ogni caso, il numero di nodi neri su questi percorsi non cambia. Per cui abbiamo ristabilito le proprietà 4 (Entrambi i figli di un nodo rosso sono neri) e 5 (Tutti i percorsi da un qualsiasi nodo alle foglie sottostanti contengono lo stesso numero di nodi neri). Il nodo bianco, nel diagramma, può essere rosso o nero, l'importante è che abbia lo stesso colore prima e dopo la trasformazione.

Di nuovo, la funzione utilizza una ricorsione di coda (mwblotail recursion), cosicché l'algoritmo è ancora in-place. Inoltre, nessuna chiamata ricorsiva viene fatta dopo una rotazione, il che rende costante il numero di rotazione (massimo 3).

Un albero rosso-nero che ha mwbl0 n {\displaystyle n} nodi interni ha un'altezza mwbl4 O ( lg ⁡ ⁡ ( n ) ) {\displaystyle O(\lg(n))} .

Definizioni:

• mwbmi h ( v ) {\displaystyle h(v)} = altezza del sottoalbero avente radice in mwbmm v {\displaystyle v} .

• mwbmu b h ( v ) {\displaystyle bh(v)} = il numero di nodi neri (non contando mwbmy v {\displaystyle v} se è nero) da mwbmc v {\displaystyle v} a qualsiasi foglia nel sottoalbero (chiamata altezza nera).

mwbmkLemma: Un sottoalbero avente radice in mwbmov ha almeno mwbms 2 b h ( v ) − − 1 {\displaystyle 2^{bh(v)}-1} nodi interni.

Dimostrazione del lemma (per induzione):

Assunto: mwbm4 h ( v ) = 0 {\displaystyle h(v)=0}

Se mwbna v {\displaystyle v} ha altezza zero deve essere vuoto, quindi mwbne b h ( v ) = 0 {\displaystyle bh(v)=0} . Per cui:

mwbnm 2 b h ( v ) − − 1 = 2 0 − − 1 = 1 − − 1 = 0 {\displaystyle 2^{bh(v)}-1=2^{0}-1=1-1=0}

Ipotesi Induttiva: mwbnu v {\displaystyle v} tale che mwbny h ( v ) = k {\displaystyle h(v)=k} , ha mwbnc 2 b h ( v ) − − 1 {\displaystyle 2^{bh(v)}-1} nodi interni implica che mwbng v ′ {\displaystyle v'} tale che mwbnk h ( v ′ ) = k + 1 {\displaystyle h(v')=k+1} ha mwbno 2 b h ( v ′ ) − − 1 {\displaystyle 2^{bh(v')}-1} nodi interni.

Dal momento che mwbnw v ′ {\displaystyle v'} ha mwbn0 h ( v ′ ) > 0 {\displaystyle h(v')>0} è un nodo interno. Ha due figli la cui altezza-nera è bh(mwbn4 v ′ {\displaystyle v'} ) o mwbn8 b h ( v ′ ) − − 1 {\displaystyle bh(v')-1} (a seconda che mwboa v ′ {\displaystyle v'} sia rosso o nero). Per ipotesi induttiva ogni figlio ha almeno mwboe 2 b h ( v ′ ) − − 1 − − 1 {\displaystyle 2^{bh(v')-1}-1} nodi interni, per cui mwboi v ′ {\displaystyle v'} ha:

mwboq 2 b h ( v ′ ) − − 1 − − 1 + 2 b h ( v ′ ) − − 1 − − 1 + 1 = 2 b h ( v ′ ) − − 1 {\displaystyle 2^{bh(v')-1}-1+2^{bh(v')-1}-1+1=2^{bh(v')}-1}

nodi interni.

Usando questo lemma possiamo dimostrare che l'altezza dell'albero è logaritmica. Dato che almeno la metà dei nodi di qualsiasi percorso dalla radice ad una foglia sono neri (proprietà 4 di un albero rosso-nero), l'altezza nera della radice è almeno h(root)/2. Dal lemma otteniamo:

mwbog n ≥ ≥ 2 h ( r o o t ) 2 − − 1 ↔ ↔ lg ⁡ ⁡ ( n + 1 ) ≥ ≥ h ( r o o t ) 2 ↔ ↔ h ( r o o t ) ≤ ≤ 2 lg ⁡ ⁡ ( n + 1 ) {\displaystyle n\geq 2^{h(root) \over 2}-1\leftrightarrow \;\lg {(n+1)}\geq {h(root) \over 2}\leftrightarrow \;h(root)\leq 2\lg {(n+1)}}

Quindi l'altezza della radice è mwboo O ( lg ⁡ ⁡ ( n ) ) {\displaystyle O(\lg(n))} .

Lmwbo0'mwbo4estensione di un RB-Albero è una pratica che consiste nell'aggiungere ai nodi informazioni aggiuntive, che consentano di supportare efficientemente altre operazioni oltre a quelle standard.

Gli mwbpaalberi di selezione T (o mwbpiorder-statistic trees), per esempio, sono alberi rosso-neri che memorizzano in ogni nodo mwbpmx la dimensione del sottoalbero radicato in mwbpqx stesso (foglie escluse). Come risultato sono in grado di ricercare un elemento con un dato rango, o determinare il rango di un elemento dato, con una complessità O(log mwbpun) nel caso pessimocite-ref-1[1].

Gli mwbpsWise Red-Black Trees garantiscono invece più efficienza nel trattare blocchi di elementi contigui. Hanno una struttura simile agli alberi di selezione T, ma i nodi memorizzano solo la dimensione del sottoalbero sinistro. Si distinguono maggiormente per le modalità di esecuzione delle operazioni principalicite-ref-2[2].

cite-note-11. ↑ mwbqcCormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford, mwbqgIntroduction to Algorithms, 3ªmwbqk ed., MIT Press, 2009 mwbqo[1990], mwbqsISBNmwbqw 978-0-262-03384-8.

cite-note-22. ↑ mwbreAlberto Boffi, mwbrimwbrmAn efficient way to manage blocks of data with Wise Red-Black Trees, Giugno 2021.

• mwbrc(EN) mwbrgSan Diego State University: CS 660: Appunti sugli alberi rosso-neri, di Roger Whitney

• mwbro(EN) mwbrsThomas H. Cormen, Charles E. Leiserson, mwbr0Ronald L. Rivest, e Clifford Stein. mwbr8mwbsaIntroduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Capitolo 13: Alberi Rosso-Neri, pp.mwbsi 273mwbsm – 301.

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sull'RB-Albero

• citerefmathworld(EN) Eric W. Weisstein, Red-Black Tree, su MathWorld, Wolfram Research.

• mwbswAnimazione di albero rosso-nero, dimostrazione del caso pessimo di inserimento

• mwbs4aiSee: Algoritmo di ordinamento, GIF animata che mostra l'inserimento (200KB)

• mwbtiRBT: Libreria per alberi rosso-neri, su efsa.sourceforge.net. URL consultato il 10 settembre 2006 (archiviato dall'url originale il 7 ottobre 2017).

• mwbtqlibredblack: Libreria C per alberi rosso-neri, su libredblack.sourceforge.net.

• mwbtyAltra implementazione C, su web.mit.edu. URL consultato il 10 settembre 2006 (archiviato dall'url originale il 14 febbraio 2008).

• mwbtgImplementazione con codice Java in java.util.TreeMap, su javaresearch.org. URL consultato il 10 settembre 2006 (archiviato dall'url originale il 20 ottobre 2007).